/**
 * Initialize your data structure here.
 */
var TimeMap = function () {
  this.map = new Map();
};
// 二分法
/**
 * @param {string} key
 * @param {string} value
 * @param {number} timestamp
 * @return {void}
 */
TimeMap.prototype.set = function (key, value, timestamp) {
  const data = [value, timestamp];
  if (this.map.has(key)) {
    const arr = this.map.get(key);
    arr.push(data);
  } else {
    this.map.set(key, [data]);
  }
};

/**
 * @param {string} key
 * @param {number} timestamp
 * @return {string}
 */
TimeMap.prototype.get = function (key, timestamp) {
  // 时间序列
  const arr = this.map.get(key);
  if (!arr) {
    return '';
  }
  let l = 0,
    r = arr.length - 1,
    m;

  // while表示满足条件
  while (l <= r) {
    // 取中位数
    m = (l + r) >> 1;
    if (arr[m][1] > timestamp) {
      r = m - 1;
    } else if (arr[m][1] < timestamp) {
      l = m + 1;
    } else {
      return arr[m][0];
    }
  }
  // r < l
  // return arr[r][0];
  // r什么时候回小于0？ 取一个非常小的时间戳的时候
  // 求得是大于timestamp的最小时间戳
  return r >= 0 ? arr[r][0] : '';
};

/**
 * Your TimeMap object will be instantiated and called as such:
 * var obj = new TimeMap()
 * obj.set(key,value,timestamp)
 * var param_2 = obj.get(key,timestamp)
 */
